\documentclass[a4paper,10pt]{article}
\usepackage{color}
% \usepackage{fancyhdr}
\usepackage[utf8]{inputenc}
\usepackage{enumerate}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{ulem}
% \usepackage{ifsym}
\usepackage{graphicx}
% \usepackage{polski}
% \usepackage[polish]{babel}
%\usepackage{a4wide}
% wstawianie obrazkow
%\usepackage{graphicx}
%\usepackage{subfig}

%\usepackage{amsmath}
%\usepackage{amsfonts}
%\usepackage{amsthm}

%\pagestyle{fancy}

%\pagestyle{fancy}

\renewcommand{\headheight}{16pt}

\newcommand{\HRule}{\rule{\linewidth}{0.1mm}}

\begin{document}

%\begin{titlepage}
\begin{center}
%	\textsc{1}\\
%	\textsc{2}\\[4cm]
% 	\HRule\\
%	\HRule \\[2cm]
	\textsc{\Large Distributed Database Systems (WS 11/12) }\\[0.3cm]
	\textsc{\large Assignment 4}\\[1cm]
        Adam Grycner\\
        Szymon Matejczyk\\[1cm]
        \today\\[1cm]
 	\HRule\\
%	\HRule\\[2cm]
	
\end{center}

\section{Exercise 3.1: Discussion}
\begin{enumerate}
 \item Order:
 \begin{enumerate}
  \item from clause - generates \textit{Cartesian product}
  \item where clause - generates \textit{selection}
  \item select clause - generates \textit{projection}
 \end{enumerate}
  \item In the end (after query execution).
  \item Algebraic query optimization is transforming query using some heuristics and additional information. Physical query optimization is choosing appropriate algorithms to execute query.
  \item 
    \begin{itemize}
     \item Considering the physical data distribution during query optimization
     \item Considering communication costs
    \end{itemize}
\end{enumerate}

\section{Exercise 3.2: Vertical fragmentation}
First of all compute (using program :D ) the attribute affinity matrix:

\[ aff = \left[ \begin{array}{ccccc}
70 & 30 & 30 & 40 & 55 \\
30 & 60 & 60 & 0 & 45 \\
30 & 60 & 70 & 0 & 45 \\
40 & 0 & 0 & 40 & 40 \\
55 & 45 & 45 & 40 & 85 \\
 \end{array} \right]\] 

The biggest ``Global affinity measure AM''  (AM value = 88950), where A1 is on the first place, has matrix (order of attributes: $A_1, A_3, A_2, A_4, A_5$):

%(96150, (5, 1, 2, 4, 3))
\[ aff = \left[ \begin{array}{c|cc|cc}
70 & 30 & 30 & 40 & 55 \\
\hline
30 & 70 & 60 & 0 & 45 \\
30 & 60 & 60 & 0 & 45 \\
\hline
40 & 0 & 0 & 40 & 40 \\
55 & 45 & 45 & 40 & 85 \\
 \end{array} \right]\] 
We divide relation into two partitions:\\
$Part1 = \pi_{A_1, A_3, A_2}(R)$\\
$Part1 = \pi_{A_1, A_4, A_5}(R)$\\


\section{Exercise 3.3: Allocation}
\begin{enumerate}[a)]
 \item 
$\begin{array}{|c|c|c|}
\hline
Fragment & Node & Accesses\\
\hline
R_1 & {\color{red} S_1} & {\color{red} 11} \\
    & S_2 & 4 \\
    & S_3 & 6 \\
    & S_3 & 1 \\
\hline
R_2 & S_1 & 5\\
    & {\color{red} S_2} & {\color{red} 20} \\
    & S_3 & 10 \\    
    & S_4 & 14 \\
\hline
R_3 & S_1 & 5\\
    & S_2 & 16 \\
    & {\color{red} S_3} & {\color{red} 15} \\    
    & S_4 & 12 \\
\hline
\end{array}$\\
Allocation: $R_1$ to $S_1$, $R_2$ to $S_2$, $R_3$ to $S_3$

\item Costs:\\
$\begin{array}{|c|c|c|c|c|}
\hline
Fragment & Node & Updt. & Costs & Total\ cost\\
\hline
R_1 & S_1 & S_1, S_2, S_3 & 150 + 600 + 600 & 1350 \\
    & S_2 & S_1, S_2, S_3 & 150 + 600 + 600 & 1350 \\
    & S_3 & S_1, S_2, S_3 & 150 + 600 + 600 & 1350 \\
    & S_4 & S_1, S_2, S_3 & 600 + 600 + 600 & 1800 \\
\hline
R_2 & S_1 & S_1, S_2, S_4 & 200 + 700 + 700 & 1600 \\
    & S_2 & S_1, S_2, S_4 & 200 + 700 + 700 & 1600 \\
    & S_3 & S_1, S_2, S_4 & 700 + 700 + 700 & 2100 \\
    & S_4 & S_1, S_2, S_4 & 200 + 700 + 700 & 1600 \\
\hline
R_3 & S_1 & S_2, S_3 & 1100 + 1100 & 2200\\
    & S_2 & S_2, S_3 & 250 + 1100 & 1350\\
    & S_3 & S_2, S_3 & 250 + 1100 & 1350\\
    & S_4 & S_2, S_3 & 1100 + 1100 & 2200\\
\hline
\end{array}$\\\\
Benefits:\\
$\begin{array}{|c|c|c|c|}
\hline
Fragment & Node & Benefit & Total\ benefit\\
\hline
R_1 & S_1 & 3*(500 - 100) & 1200\\
    & S_2 & 5*(500 - 100) & 2000\\
    & S_3 & 1*(500 - 100) & 400\\
    & S_4 & 0*(500 - 100) & 0\\
\hline
R_2 & S_1 & 7*(650 - 150) & 3500\\
    & S_2 & 2*(650 - 150) & 1000\\
    & S_3 & 0*(650 - 150) & 0 \\
    & S_4 & 3*(650 - 150) & 1500\\
\hline
R_3 & S_1 & 0*(1000 - 200) & 0\\
    & S_2 & 1*(1000 - 200) & 800\\
    & S_3 & 5*(1000 - 200) & 4000 \\
    & S_4 & 0*(1000 - 200) & 0\\
\hline
\end{array}$\\
Differences:\\
$\begin{array}{|c|c|c|c|}
\hline
Fragment & Node & Total\ cost & Total\ benefit\\
\hline
R_1 & S_1 & 1350 & 1200\\
    & {\color{red} S_2} & {\color{red} 1350} & {\color{red} 2000}\\
    & S_3 & 1350 & 400\\
    & S_4 & 1800 & 0\\
\hline
R_2 & {\color{red} S_1} & {\color{red} 1600} & {\color{red} 3500}\\
    & S_2 & 1600 & 1000\\
    & S_3 & 2100 & 0 \\
    & S_4 & 1600 & 1500\\
\hline
R_3 & S_1 & 2200 & 0\\
    & S_2 & 1350 & 800\\
    & {\color{red} S_3} & {\color{red} 1250} & {\color{red} 4000} \\
    & S_4 & 2200 & 0\\
\hline
\end{array}$\\
Allocation: $R_1$ to $S_2$, $R_2$ to $S_3$, $R_3$ to $S_3$
\item The same as in \textit{all beneficial nodes method}, because we have not allocated more than one copy.
\end{enumerate}

\end{document}
